import java.util.Arrays;

/**
 * Simple hash table implementation contains integers as keys and 
 * integers as values. Implementation provides two parameters affect its
 * performance <i>capacity</i> and <i>threshold</i>. The <i>capacity</i> is
 * initial number of buckets in the table. The <i>threshold</i> is a measure 
 * of how full the hash table is allowed to get before its capacity is 
 * automatically increased.
 * Value FREE_CELL (Integet.MIN_VALUE) is reserved for mark buckets as free.
 * @author Artem Nikitin
 *
 */
public class IntegerHashMap {
	
	public static final int FREE_CELL = Integer.MIN_VALUE;
	private int[] keys;
	private int[] values;
	private int size;
	private int capacity;
	private double threshold;
	
	/**
	 * Constructs integer hash table with specified capacity and threshold
	 * @param capacity - initial capacity
	 * @param threshold - threshold.
	 */
	public IntegerHashMap(int capacity, double threshold) {
		this.capacity = capacity;
		this.threshold = threshold;
		keys = new int[capacity];
		values = new int[capacity];
		Arrays.fill(keys, FREE_CELL);
	}
	
	/**
	 * Constructs integer hash table with specified capacity and default threshold (0.9);
	 * @param capacity - initial capacity
	 */
	public IntegerHashMap(int capacity) {
		this(capacity, 0.9);
	}
	
	/**
	 * Constructs integer hash table with default capacity (16) and default threshold(0.9)
	 */
	public IntegerHashMap() {
		this(16, 0.9);
	}

	/**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>FREE_CELL</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>FREE_CELL</tt> return can also indicate that the map
     *         previously associated <tt>FREE_CELL</tt> with <tt>key</tt>.)
     */
	public int put(int key, int value) {
		if (key == FREE_CELL) {
			throw new IllegalArgumentException("key value \"" + FREE_CELL + "\" is reserved and cannot be used");
		}
		
		if ((double) size() / capacity >= threshold) {
			rehash();
		}
		
		for(int i = index(key); ; i++) {
			if (i == capacity) {
				i = 0;
			}
			
			if (keys[i] == FREE_CELL) {
				keys[i] = key;
				values[i] = value;
				size++;
				return FREE_CELL;
			}
			
			if (keys[i] == key) {
				int oldValue = values[i];
				values[i] = value;
				return oldValue;
			}
		}
	}
	
	/**
	 * Returns the value to which the specified key is mapped,
     * or {@code FREE_CELL} if this map contains no mapping for the key.
	 * @param key the key whose associated value is to be returned
	 * @return the value to which the specified key is mapped, or
     *         {@code FREE_CELL} if this map contains no mapping for the key
	 */
	public int get(int key) {
		if (key == FREE_CELL) {
			throw new IllegalArgumentException("key value \"" + FREE_CELL + "\" is reserved and cannot be used");
		}
		
		for(int i = index(key); ; i++) {
			if (i == capacity) {
				i = 0;
			}
			
			if (keys[i] == FREE_CELL) {
				return FREE_CELL;
			}
			
			if (keys[i] == key) {
				return values[i];
			}
		}
	}
	
	/**
	 * Removes all of the mappings from this map.
     * The map will be empty after this call returns.
	 */
	public void clear() {
		Arrays.fill(keys, FREE_CELL);
	}

	/**
	 * Returns <tt>true</tt> if this map contains a mapping for the specified key.
	 * @param key key whose presence in this map is to be tested
	 * @return <tt>true</tt> if this map contains a mapping for the specified
     *         key
	 */
	public boolean containsKey(int key) {
		return get(key) != FREE_CELL;
	}
	
	 /**
     * Returns <tt>true</tt> if this map maps one or more keys to the
     * @param value value whose presence in this map is to be tested
     * @return <tt>true</tt> if this map maps one or more keys to the
     *         specified value
     */
	public boolean containsValue(int value) {
		for (int i = 0; i < values.length; i++)
			if (values[i] == value && keys[i] != FREE_CELL) 
				return true;
		return false;
	}
	
    /**
     * Rehashes the contents of this map into a new array with a
     * larger capacity.  This method is called automatically when the
     * number of keys in this map reaches its threshold.
     */
	private void rehash() {
		int oldCapacity = capacity;
		int[] oldKeys = keys;
		int[] oldValues = values;
		capacity *= 2;
		keys = new int[capacity];
		values = new int[capacity];
		Arrays.fill(keys, FREE_CELL);
		Arrays.fill(values, FREE_CELL);
		size = 0;
		for (int i = 0; i < oldCapacity; i++) {
			if (oldKeys[i] != FREE_CELL) {
				put(oldKeys[i], oldValues[i]);
			}
		}
	}
	
	/**
     * Returns the number of key-value mappings in this map.
     *
     * @return the number of key-value mappings in this map
     */
	public int size() {
		return size;
	}
	
	/**
     * Returns the current capacity of this map.
     *
     * @return the current capacity of this map
     */
	public int capacity() {
		return capacity;
	}
	
	/**
     * Returns index for hash code {@code hash}.
     */
	private int index(int hash) {
		return Math.abs(hash) % capacity;
	}
	
}
